漫画:二分解题模板(第一讲)- 修订版
今天还是小浩算法“365刷题计划”第66天。昨天也是第66天,为什么?因为昨天我的内容忘记标识原创,马上就被人抄袭到了自己的博客,我很不爽!当然,经过投诉,对方已经删文。所以为了防止再次抄袭,我决定重新发布一下昨天的文章。考虑到本文有朋友已经学习过了,所以我在原有的基础上进行了加强,并且答疑了昨天私下有人问我的几个问题,不妨看一看!暂定后续要讲解的几个topic为:二分法(以常考题目为主)、回溯法(大部分是中等以上难度题型)、分治法(以思想掌握为主)、动态规划(以2维DP为主)、其他。希望大家可以长期支持!一起学习,共同进步。
01PART题目分析
不知道为什么叫做爱吃香蕉的阿珂,难道不应该是爱吃香蕉的猴子么...或者爱吃队友的露娜么?
第875题:阿珂喜欢吃香蕉。这里总共有 N 堆香蕉,第 i 堆中有piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。 阿珂可以决定她吃香蕉的速度 K (单位:根/小时),每个小时,她将会选择一堆香蕉,从中吃掉 K 根。
如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。
(阿珂可能长这样)
PS:建议大家停留个两分钟先想一想...直接拉下去看题解就没什么意思了。
02PART二分查找
十个二分九个错,该算法被形容 "思路很简单,细节是魔鬼"。第一个二分查找算法于 1946 年出现,然而第一个完全正确的二分查找算法实现直到 1962 年才出现。下面的二分查找,其实是二分查找里最简单的一个模板,在后面的文章系列里,我将逐步为大家讲解二分查找的其他变形形式。
二分查找是计算机科学中最基本、最有用的算法之一。它描述了在有序集合中搜索特定值的过程。一般二分查找由以下几个术语构成:
目标 Target —— 你要查找的值
索引 Index —— 你要查找的当前位置
左、右指示符 Left,Right —— 我们用来维持查找空间的指标
中间指示符 Mid —— 我们用来应用条件来确定我们应该向左查找还是向右查找的索引
在最简单的形式中,二分查找对具有指定左索引和右索引的连续序列进行操作。我们也称之为查找空间。二分查找维护查找空间的左、右和中间指示符,并比较查找目标;如果条件不满足或值不相等,则清除目标不可能存在的那一半,并在剩下的一半上继续查找,直到成功为止。
举例说明:比如你需要找1-100中的一个数字,你的目标是用最少的次数猜到这个数字。你每次猜测后,我会说大了或者小了。而你只需要每次猜测中间的数字,就可以将余下的数字排除一半。
不管我心里想的数字如何,你在7次之内都能猜到,这就是一个典型的二分查找。每次筛选掉一半数据,所以我们也称之为 折半查找。一般而言,对于包含n个元素的列表,用二分查找最多需要log2n步。
当然,一般题目不太可能给你一个如此现成的题型,让你上手就可以使用二分,所以我们需要思考,如何来构造一个成功的二分查找。大部分的二分查找,基本都由以下三步组成:
预处理过程(大部分场景就是对未排序的集合进行排序)
二分查找过程(找到合适的循环条件,每一次将查找空间一分为二)
后处理过程(在剩余的空间中,找到合适的目标值)
了解了二分查找的过程,我们对二分查找进行一般实现(这里给出一个Java版本,比较正派的代码,没有用一些缩写形式)
1//JAVA
2public int binarySearch(int[] array, int des) {
3 int low = 0, high = array.length - 1;
4 while (low <= high) {
5 int mid = low + (high - low) / 2;
6 if (des == array[mid]) {
7 return mid;
8 } else if (des < array[mid]) {
9 high = mid - 1;
10 } else {
11 low = mid + 1;
12 }
13 }
14 return -1;
15}
注意:上面的代码,mid 使用 low + (high - low)/2 的目的,是防止 high+low 溢出内存。
为什么说是一般实现?
1、根据边界的不同(开闭区间调整),有时需要弹性调整low与high的值,以及循环的终止条件。
2、根据元素是否有重复值,以及是否需要找到重复值区间,有时需要对原算法进行改进。
那上面我们说了,一般二分查找的过程分为:预处理 - 二分查找 - 后处理,上面的代码,就没有后处理的过程,因为在每一步中,你都检查了元素,如果到达末尾,也已经知道没有找到元素。
总结一下一般实现的几个条件:
初始条件:
left = 0, right = length-1
终止:
left > right
向左查找:
right = mid-1
向右查找:
left = mid+1
请大家记住这个模板原形,在后面的系列中,我们将介绍二分查找其他的模板类型。
03PART题目分析
简单复习了二分查找,我们来看本题。
注意,绝大部分「在递增递减区间中搜索目标值」 的问题,都可以转化为二分查找问题。并且,二分查找的题目,基本逃不出三种:找特定值,找大于特定值的元素(上界),找小于特定值的元素(下界)。
而根据这三种,代码又最终会转化为以下这些问题:
low、high 要初始化为 0、n-1 还是 0、n 又或者 1,n?
循环的判定条件是 low < high 还是 low <= high?
if 的判定条件应该怎么写?
if 条件正确时,应该移动哪边的边界?
更新 low 和 high 时,mid 如何处理?
处理好了上面的问题,自然就可以顺利解决问题。将上面的思想代入到本题,我们要找 “阿珂在 H 小时吃掉所有香蕉的最小速度 K”。那最笨的就是阿珂吃的特别慢,每小时只吃掉 1 根香蕉,然后我们逐渐递增阿珂吃香蕉的速度到 i,刚好满足在 H 小时可以吃掉所有香蕉,此时 i 就是我们要找的最小速度。当然,我们没有这么笨,所以可以想到使用二分的思想来进行优化。
然后就简单了,我们寻找二分查找模板中初始条件和终止条件(注意,这里的 high、low、mid 都代表的是速度):
1//这里我把最小速度定义成了1,可能大家会觉得奇怪,模板里不是0吗?
2//所以这里我其实是想说,算法千变万化,大家不要生搬硬套。
3//从字面理解,如果定义成0,意味着阿珂会选择一个香蕉都不吃,难道阿珂傻?
4var low = 1
5//最大的速度,当然等于吃掉最大一堆的香蕉,毕竟一小时只能吃一堆,再大也没有意义
6var high = maxArr(piles)
7//中间速度
8var mid = (low + high) / 2
1//java
2public class Solution {
3 public int minEatingSpeed(int[] piles, int H) {
4 int maxVal = 1;
5 for (int pile : piles) {
6 maxVal = Math.max(maxVal, pile);
7 }
8 int left = 1;
9 int right = maxVal;
10 while (left < right) {
11 int mid = (left + right) >> 1;
12 if (canEat(piles, mid, H)) {
13 left = mid + 1;
14 } else {
15 right = mid;
16 }
17 }
18 return left;
19 }
20
21 private boolean canEat(int[] piles, int speed, int H) {
22 int sum = 0;
23 for (int pile : piles) {
24 //向上取整
25 sum += (pile + speed - 1) / speed;
26 }
27 return sum > H;
28 }
29}
(看起来还是不错的)
郑重申明(读我的文章必看):
本系列所有教程都不会用到复杂的语言特性,大家无须担心没有学过相关语法,算法思想才是最重要的!
作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode进行过测试运行。
额外补充(昨天有人问我的问题):
第一:就是不需要再对原数组进行排序了,因为我们是把这样一个问题转化为二分查找的问题,而通过 canEat,计算在 mid 速度下吃完 piles 共需要多少小时。已经将 piles 利用进去了,所以此时并不需要对 piles 排序。
第二:就是昨天有人私下问我,对 (pile + speed - 1)/speed 不能理解。这个其实就是向上取整的一个小技巧,相当于 Math.ceil(pile * 1.0 / speed)。
留下一个问题,假如我们的阿珂就是笨笨的,将 low 初始化成了 0,此时的循环条件应该如何写?if 条件如果成立,low 和 high 又该如何进行调整?大家可以尝试一下!(一百个人有一百个二分,不要妄图和别人写出一模一样的代码,这是没有意义的。只有自己理解了,一步步的分析问题,写出自己的代码,才是真正属于你的)
所以,今天的问题你学会了吗?评论区留下你的想法!
小浩算法,每日一题
关注领取《图解算法》高清版
进群的小伙伴请加右侧私人微信(备注:进群)